//
// Created by 抑~风 on 2022/11/20.
//

#ifndef CWJ_COMPILER_REGEXP_H
#define CWJ_COMPILER_REGEXP_H

#include <utility>
#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<memory>
#include<cmath>
using namespace std;
namespace CWJ {

    class CompilerUtil {
    public:
        bool isBlank(char c);

        bool isAnnotation(const string &str);

        bool trim(string &line);

        bool readRule(const string &path, vector<string> &rules);


    private:

    };

    /**
     * class Token
     * */

    template<typename T, typename ContextType>
    class Token {
    public:
        // 构造函数
        Token() = default;

        Token(const T &type, unsigned int uid, const ContextType &text);

        // getter / setter
        T getType() const;

        size_t getUid() const;

        const ContextType &getConText() const;

        bool operator == (const Token&);

    private:
        // token 的类型，一般为对应词法分析的枚举类型
        T type;
        size_t uid;
        // 内容，即token的内容，文本
        ContextType context;
    };

    template<typename T, typename ContextType>
    class Token_hash
    {
    public:
        size_t operator()(const Token<T,ContextType>& rc)const
        {
            return hash<decltype(rc.getType())>()(rc.getType()) ^ hash<decltype(rc.getConText())>()(rc.getConText()) ^ hash<decltype(rc.getUid())>()(rc.getUid());
        }

    };


    /**
     * class RegexpLever
     * */

    class RegexpLever {
    public:
        enum class TokenType {
            OR,
            STR,
            CHAR,
            BETWEEN,
            LEFT_SMALL,
            RIGHT_SMALL,
            LEFT_MIDDLE,
            RIGHT_MIDDLE,
            PLUS,
            QUESMARK,
            ASTERISK,
            OPPOSITE,
            TRANSFORM,
            DOT,
        };
        using TokenList = std::vector<Token<RegexpLever::TokenType, char>>;


        TokenList tokenize(const std::string &script);

    private:
        static std::unordered_map<char, TokenType> SPECIAL_SYMBOL_MAP;
        TokenList tokens;
    };

    /**
     * class ASTNode
     * */

    template<typename NodeType, typename Context>
    class ASTNode {
    public:
        using size_t = std::size_t;
        using ASTNodePtr = std::shared_ptr<ASTNode<NodeType, Context>>;
        using Childs = std::vector<ASTNodePtr>;

        ASTNode() = default;

        ASTNode(NodeType type, Context context);

        void addChild(NodeType nodeType, const Context &context);

        void addChild(ASTNode *son);

        void addChild(ASTNodePtr son);

        NodeType getType() const;

        const Childs &getChilds() const;

        Context getContext() const;

        void setContext(Context context);

        void setType(NodeType type);

        void setChilds(const Childs &childs);

        virtual ~ASTNode() = default;

    private:
        // 其一般是某个语法分析场景下的枚举类类型
        NodeType type;
        Childs childs;
        // 内容，即节点需要持有的内容
        Context context;


    };

    /**
     * class CharSet
     * */
    class CharSet {
    public:

        static const int INF = 0x3f3f3f3f;

        static const CharSet EPSILON_CharSet;

        explicit CharSet(uint32_t from, uint32_t to, bool isOppo = false) : from(from), to(to), isOpposite(isOppo) {};

        uint32_t getFrom() const;

        uint32_t getTo() const;

        void setIsOpposite(bool isOpposite);

        bool isOpposite1() const;

    private:
        uint32_t from{0};
        uint32_t to{0};
        // 是否取补集
        bool isOpposite;
    };

    /**
     * class RegexParser
     * */
    class RegexParser {
    public:

        // 构建得到的语法树的结点类类型中不同的类型
        // 即ASTNode类型的节点还分为三种不同类型OR,AND,CHARSET
        enum class NodeType {
            OR,
            AND,
            CHARSET,
        };
        // 构建得到的语法树的结点的类类型
        using ASTBaseNode = CWJ::ASTNode<RegexParser::NodeType, CWJ::CharSet>;

        class ASTNode : public ASTBaseNode {
        public:
            using size_t = std::size_t;

            ASTNode(const RegexParser::NodeType &nodetype, const CharSet &charSet);

            int getMaxTime() const;

            void setMaxTime(size_t maxTime);

            int getMinTime() const;

            void setMinTime(size_t minTime);

            bool isGreedy1() const;

            void setIsGreedy(bool isGreedy);

        private:
            int maxTime{1};
            int minTime{1};
            bool isGreedy{true};
        };

        using ASTNodePtr = std::shared_ptr<RegexParser::ASTNode>;
        using ASTBaseNodePtr = std::shared_ptr<RegexParser::ASTBaseNode>;
        // 要解析的tokens类型
        using TokenType = RegexpLever::TokenType;

        static ASTNodePtr EPSILON_ASTNode;

        ASTNodePtr parse(const RegexpLever::TokenList &tokens);

    private:

        ASTBaseNodePtr nodePtr2BaseNodePtr(ASTNodePtr);

        ASTNodePtr baseNodePtr2NodePtr(ASTBaseNodePtr);

        ASTNodePtr dfs_parse_or(int &ind, const RegexpLever::TokenList &tokens);

        ASTNodePtr dfs_parse_and(int &ind, const RegexpLever::TokenList &tokens);

        ASTNodePtr dfs_parse_str(int &ind, const RegexpLever::TokenList &tokens);

        ASTNodePtr dfs_parse_middle(int &ind, const RegexpLever::TokenList &tokens);

        // 构建得到的树的根结点
        ASTNodePtr root;
    };

    /**
     * class NfaEdge
     * */
    class NfaEdge {
    public:
        using ASTNodePtr = RegexParser::ASTNodePtr;
        using ASTNode = RegexParser::ASTNode;

        NfaEdge() = default;

        NfaEdge(NfaEdge::ASTNodePtr filter) : filter(std::move(filter)) {}

        bool isFilterNull();

        bool match(char a);

        ASTNodePtr getFilter() const;

        bool isEPSILON();

    private:
        ASTNodePtr filter;
    };

    /**
     * class NfaNode
     * */
    class NfaNode {

    public:

        using NfaNodePtr = std::shared_ptr<NfaNode>;

        NfaNode() { uid = ++id; };

        NfaNode(bool isAc) : isAc(isAc) { uid = ++id; }

        void addVer(NfaNodePtr, NfaEdge);

        bool isAc1() const;

        void setIsAc(bool isAc);

        unsigned int getUid() const;

        bool isGreedy1() const;

        void setIsGreedy(bool isGreedy);

        const unordered_map<NfaNodePtr, vector<NfaEdge>> &getVers() const;

        const vector<NfaNodePtr> &getEdgesOrder() const;

    private:
        static unsigned int id;
        bool isAc{false};
        bool isGreedy{true};
        unordered_map<NfaNodePtr, vector<NfaEdge>> vers{};
        vector<NfaNodePtr> edgesOrder;
        unsigned int uid;
    };

    /**
     * class NfaGraph
     * */
    class NfaGraph {
    public:
        using NfaNode = CWJ::NfaNode;
        using NfaNodePtr = NfaNode::NfaNodePtr;
        using PNN = pair<NfaNodePtr, NfaNodePtr>;
        using ASTNodePtr = NfaEdge::ASTNodePtr;
        using ASTNode = NfaEdge::ASTNode;
        using NodeType = RegexParser::NodeType;

        void regexAST2nfaGraph(ASTNodePtr root);

        NfaNodePtr getStartState() const;

        NfaNodePtr getEndState() const;

        void setStartState(NfaGraph::NfaNodePtr startState);

        void setEndState(NfaGraph::NfaNodePtr endState);

    private:

        PNN regexAST2nfaGraphDfs(ASTNodePtr root);

        NfaNodePtr startState;
        NfaNodePtr endState;

    };

    /**
     * class CWJLever
     * */
    class CWJLever {
    public:

        using TokenList = vector<Token<string, string>>;
        using Token = CWJ::Token<string, string>;

        TokenList tokenize(string script);

        bool readRule(string);

        void updateNfaGraph();

        const NfaGraph &getGraph() const;

    private:
        void clear();

        bool tokenize(string &script, NfaGraph::NfaNodePtr state, int ind, int &start,
                      unordered_set<NfaGraph::NfaNodePtr> &st);

        CompilerUtil cUtil;
        NfaGraph graph;
        unordered_map<string, string> ruleMap;
        // 接收状态 -> 对于token
        unordered_map<NfaGraph::NfaNodePtr, string> tokenMap;
        vector<string> ruleOrders;
        TokenList tokens;
    };

    class GrammarLever {
    public:
        using Token = CWJLever::Token;
        using TokenList = CWJLever::TokenList;

        GrammarLever(string ruleFilePath);

        GrammarLever() = default;

        const string &getRuleFilePath() const;

        void setRuleFilePath(const string &ruleFilePath);

        TokenList tokenize(string script);

    private:
        CWJLever lever;
        string ruleFilePath;

    };


    //         对于该类型，要么可以继承ASTNode<>来实现，或是在建一个context结构体充当ASTNode的类型
    class ResASTNode {
    public:
        enum class NodeType {
            TOKEN,
            IDENT,
            OPERATOR,
            EPSILON,
        };
        using ResASTNodePtr = ResASTNode *;

        ResASTNode(const enum NodeType &nodeType, const string &context,const string &val);

        void addChild(ResASTNodePtr son);

        NodeType getNodeType() const;

        void setNodeType(NodeType nodeType);

        const string &getContext() const;

        void setContext(const string &context);

        const vector<ResASTNodePtr> &getChilds() const;

        void setChilds(const vector<ResASTNodePtr> &childs);

        const string &getVal() const;

        void setVal(const string &val);

        static void showResASTNode(ResASTNode::ResASTNodePtr root, string text);

        static void
        showResASTNode(ResASTNode::ResASTNodePtr root, string text, unordered_set<ResASTNode::ResASTNodePtr> &st);

        static ResASTNodePtr EPSILON_NODE;


    private:
        NodeType type;
        string context;
        string val {""};
        // 终止符：token类型，NodeType = TOKEN ，context = 对应词法分析得到的token类型，可以为空，或对应值
        // 非终止符：NodeType = IDENT | OPERATOR，而context填写 = 对于非终止符的名字
        // name2child : 即通过非终止符类型检索到对应的子节点，但是不包括终止符，即token,原因是为了便于后面自定义的语义分析
        unordered_map<string, ResASTNodePtr> identName2child;
        // 子节点
        vector<ResASTNodePtr> childs;


    };


    template<typename Tval>
    struct Ptr_hash{
        size_t operator()(Tval val) const {
//            static const size_t shift = (size_t)log2(1 + sizeof(Tval));
            return (size_t)(val) >> 4;
        }
    };


//equal相当于重载operator==
// int->string  to_string
//string temp = to_string(rc1.name)
    template<typename T>
    struct Ptr_equal {
        bool operator()(T rc1, T rc2) const noexcept {
            return (size_t)rc1 == (size_t)rc2;
        }
    };

    class GrammarParser {
    public:
        enum class NodeType {
            OR,
            AND,
            TOKEN,
        };
        struct Context {
            int maxTime{1};
            int minTime{1};
            // 对于Token节点，该值存储token类型值，对于OR/AND类型节点，该值存储标识符名字
            string text;
        };


        using ASTNode = CWJ::ASTNode<NodeType, Context>;
        using ASTNodePtr = ASTNode *;

        using ResASTNode = CWJ::ResASTNode;

        using ResASTNodePtr = ResASTNode::ResASTNodePtr;

        using Token = GrammarLever::Token;
        using TokenList = GrammarLever::TokenList;

        using FirstSet = unordered_set<string>;
        using FollowSet = FirstSet;

        explicit GrammarParser(const string &grfPath = "PlayScript.txt");

        void init();

        bool readRuleFile(string);

        ResASTNodePtr parse(const TokenList&);
        ResASTNodePtr parseLL1(const TokenList&);

    private:
        ResASTNodePtr
        parse(const TokenList& tokens, int &ind, unordered_map<ASTNodePtr, int> &st, GrammarParser::ASTNodePtr node,
              int &count);
        ResASTNodePtr parseLL1(const TokenList& tokens, int &ind, unordered_map<ASTNodePtr, int> &st, GrammarParser::ASTNodePtr node,
                            int &count);

        ASTNodePtr updateRuleTree(const string &name);

        ASTNodePtr dfs_parse_or(const TokenList &tokens, int &start);

        ASTNodePtr dfs_parse_and(const TokenList &tokens, int &start);

//        ASTNodePtr dfs_parse_prim(const TokenList& tokens,int& start);
        ASTNodePtr dfs_parse_prim(const TokenList &tokens, int &ind);

        void caluFirstSet();
        bool caluFirstSet(ASTNodePtr root,unordered_set<ASTNodePtr>&);
        void caluFollowSet();
        bool caluFollowSet(ASTNodePtr root,unordered_set<ASTNodePtr>&);
        FollowSet &caluFoGetFollow(ASTNodePtr);
        FirstSet &caluFiGetFirst(ASTNodePtr);
        void calcuFirstSetIsInsert(FirstSet &firstSet, const ASTNode::ASTNodePtr &son);


        GrammarLever lever{"parser_rule.txt"};
        CompilerUtil cUtil;
        string grfPath;
//        TokenList tokens;
        // 上下文语法规则
        unordered_map<string, string> name2rule;
        vector<string> n2rOrders;
        // parse rule
        unordered_map<string, ASTNodePtr> name2tree;
        vector<string> r2tOrder;
        // token_map
        unordered_map<string, Token> type2token;

        // firstSet,followSet

        unordered_map<ASTNodePtr,FirstSet ,Ptr_hash<ASTNodePtr>,Ptr_equal<ASTNodePtr>>firstSets;
        unordered_map<ASTNodePtr,FollowSet,Ptr_hash<ASTNodePtr>,Ptr_equal<ASTNodePtr>>followSets;

        ASTNodePtr rootNode;

        static string ROOT_NODE_NAME;
        static string END_SIGN;

    };



    /*-----------------------------------------------------------------*/


    /**
     *  Token methods
     * */

    template<typename T, typename ContextType>
    Token<T, ContextType>::Token(const T &type, unsigned int uid, const ContextType &text) : type(type), uid(uid),
                                                                                             context(text) {}

    template<typename T, typename ContextType>
    T Token<T, ContextType>::getType() const {
        return type;
    }

    template<typename T, typename ContextType>
    size_t Token<T, ContextType>::getUid() const {
        return uid;
    }

    template<typename T, typename ContextType>
    const ContextType &Token<T, ContextType>::getConText() const {
        return context;
    }

    template<typename T, typename ContextType>
    bool Token<T, ContextType>::operator==(const Token &t) {
        return this->type == t.type && this->context == t.context;
    }

    /**
     * ASTNode methods
     * */

    template<typename NodeType, typename Context>
    ASTNode<NodeType, Context>::ASTNode(NodeType type, Context text) : type(type), context(std::move(text)) {};

    template<typename NodeType, typename Context>
    void ASTNode<NodeType, Context>::addChild(NodeType nodeType, const Context &text) {
        this->childs.emplace_back(nodeType, text);
    }

    template<typename NodeType, typename Context>
    void ASTNode<NodeType, Context>::addChild(ASTNodePtr son) {
        this->childs.push_back(son);
    }

    template<typename NodeType, typename Context>
    void ASTNode<NodeType, Context>::addChild(ASTNode *son) {
        std::shared_ptr<ASTNode> ptr(son);
        this->childs.push_back(ptr);
    }

    template<typename NodeType, typename Context>
    NodeType ASTNode<NodeType, Context>::getType() const {
        return type;
    }

    template<typename NodeType, typename Context>
    const typename ASTNode<NodeType, Context>::Childs &ASTNode<NodeType, Context>::getChilds() const {
        return childs;
    }

    template<typename NodeType, typename Context>
    Context ASTNode<NodeType, Context>::getContext() const {
        return context;
    }

    template<typename NodeType, typename Context>
    void ASTNode<NodeType, Context>::setContext(Context context) {
        ASTNode::context = context;
    }

    template<typename NodeType, typename Context>
    void ASTNode<NodeType, Context>::setType(NodeType type) {
        ASTNode::type = type;
    }

    template<typename NodeType, typename Context>
    void ASTNode<NodeType, Context>::setChilds(const ASTNode::Childs &childs) {
        ASTNode::childs = childs;
    }


};

#endif //CWJ_COMPILER_REGEXP_H
